\section{Controlling negative diffusion}
\label{sec:intro.game}
In this section, we motivate our problems using computer virus as an
example. However the study of intervention strategies can be easily
applied to other fields like epidemiology.

Over the recent decades, there has been an explosive growth in the use
of personal digital devices of various kinds, which are connected to
the Internet through new technologies, such as Bluetooth and Wi-Fi to
allow ubiquitous access. This has, unfortunately, been accompanied by
significant increase in worm attacks that exploit bugs in these new
technologies, and which have new and growing ``medium'' to spread on -
recent attacks, e.g., Cabir and CommWorm, that span multiple networks
are expected to become increasingly prevalent in future. While,
effective anti-virus software and patches are readily available, the
average user is very independent and does not often care to be
proactive about installing the most effective anti-virus software, and
downloading the latest patches, partially because of the cost of the
software and the effort involved, which we refer to as the {\em
  security cost}.  Indeed, a large fraction of devices are estimated
to be without adequate anti-virus protection. If a user does not
install protective software, they would incur a cost if his device
gets attacked, due to downtime, loss of revenue, and cost of
re-installing systems; we refer to these as the {\em infection
  cost}. If enough other nodes in the network are secured, the
likelihood of a specific device getting infected would go down (as a
result of the ``herd immunity''), leading to a natural game theoretic
scenario. A number of different non-cooperative game formulations have
been developed to study this basic problem, e.g.,
\cite{AspnesCY2006,aspnes07,berger05,ganesh05,grossklags,lelarge+b:security,wang03};
one issue with many of these formulations is that they involve utility
functions that require quite a lot of non-local information to
compute, and it is not clear how implementable such games might be.

%% our results
In this thesis, we present a generalized network security game model
$\GNS{d}$, which incorporates arbitrary contact networks through an
undirected graph $G$ and heterogeneous nodes with individual security
and infection costs.  Our model is parametrized by network locality
parameter $d$, which represents the distance within the network that a
given infection can spread.  Equivalently, the parameter $d$ in the
game $\GNS{d}$ could represent the extent of neighborhood information
that is available to a node when making strategic security decisions,
which is a departure from earlier models which require global
information for making decisions.  Qualitatively, we consider three
important cases with respect to $d$.  The case $d = 1$, which we refer
to as the {\em local infection model}, is most well-suited for ad hoc
wireless networks and social networks, when certain actions initiated
by an insecure node could adversely affect immediate neighbors,
friends, or email contacts.  For this case, our model can be viewed as
a variant of the IDS model of~\cite{kearns:ids}.  The case $d =
\infty$, which we refer to as the {\em global infection model}, is
most well-suited for the highly infectious worms and viruses in the
Internet that can be transmitted in an hop-unlimited manner through
unsuspecting insecure nodes, under the assumption that individual
nodes have complete information.  Our $\GNS{\infty}$ model is a
generalization of the elegant model of~\cite{AspnesCY2006}.  The
intermediate case $1 < d < \infty$ applies to the majority of network
security hazards where the transmission may be hop-limited and nodes
may only have limited local information about the topology and
security decisions taken by others. Our main results are the
following.
\begin{itemize}
\item
{\bf Existence of pure Nash equilibria (NE):} We show that the locality
parameter $d$ plays a significant role in the structure of the
resulting games.  Both the extremes of $\GNS{1}$ and $\GNS{\infty}$
turn out to be ordinal potential games, and a pure NE can be computed
by best response dynamics -- that is, every sequence of best response
steps by the individual players converges to a pure NE. However, for
every $d$ in the range $(1, \infty)$, there exists an instance of
$\GNS{d}$ that does not have a pure equilibrium.  The price of anarchy
for a $\GNS{1}$ game is at most the maximum degree of the contact
graph, while that for $\GNS{\infty}$ is inversely proportional to
the vertex expansion of the contact graph.
\item
{\bf Complexity of computing pure NE:} While there is a simple
combinatorial characterization for the existence of pure NE in
$\GNS{d}$ for all $d$, we show that for $1<d<\infty$, deciding if an
arbitrary instance of $\GNS{d}$ has a pure NE is NP-complete.  For
$\GNS{1}$, we show that finding a pure NE of least cost is
NP-complete; a corresponding result for $\GNS{\infty}$ is
in~\cite{AspnesCY2006}.
\item
{\bf Approximating the social optimum:} We show that computing the
social optimum is NP-complete for a $\GNS{d}$ game, for any $d$; the
case of $d=\infty$ was shown by \cite{AspnesCY2006}.  We design a
general framework for finding a strategy vector for the players in
polynomial time, whose cost is at most $2d$ times that of the optimal,
for any fixed $d$.  In particular, this implies that for $d = 1$, we
obtain a $2$-approximation.  For $d=\infty$, we provide a different
algorithm within the framework that yields an $O(\log
n)$-approximation, where $n$ is the number of nodes in the network;
this improves on the approximation bound of $O(\log^{1.5}{n})$ of
\cite{AspnesCY2006} achieved for a special case of the $\GNS{\infty}$.
\item
{\bf Empirical results:} We study the characteristics of NE
empirically in two distinct classes of graphs: random geometric graphs
and power law graphs. For $d=1$, we find that the convergence time for
best response is sub-linear in the number of nodes in both the classes
of graphs, while it is linear for $d=\infty$.  Also, for $d=1$, we
find that the cost of the pure NE obtained is very close to that of
the social optimum, indicating that the pure NE obtained in real-world
networks approximate social optimum very well.  For $d=\infty$, we
observe that there may be a significant gap between the cost of the pure
NE and that of the social optimum, even for small networks.  Finally,
we study the performance of our approximation algorithms for the
social optimum, and find that the approximation guarantees in practice
are much smaller than our theoretical bounds.
\end{itemize}

Pure NE represent stable operating points for a system with selfish
users. Therefore, for a network planner, understanding and controlling
the quality of equilibria reached is an important issue.  Our results
suggest locality characteristics of the network or the amount of
information available to the strategic network players have a
significant impact on the existence of equilibria.  The
non-monotonicity in the existence of NE, with respect to $d$, is
somewhat surprising and suggests a closer examination of the impact of
information on pure NE in such games.  While our theoretical analysis
indicates that pure NE may be significantly inferior to the optimum in
terms of social optimum in the worst-case, our experiments suggest
that for real-world network models pure NE obtained by uncoordinated
best response dynamics have low cost relative to the social optimum,
especially in the case of $d=1$.  Additionally, our results on the
price of anarchy suggest natural heuristics to aid a network planner
in enforcing efficient equilibria. Finally, the approximations
achieved by our approximation algorithms, both in theory and
experiments, indicate that our proposed algorithms are viable
candidates wherever centralized decisions can be made on network
protection mechanisms.
